package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/trim-a-binary-search-tree/">修剪二叉搜索树(Trim a Binary Search Tree)</a>
 * <p>
 * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树<b>不应该</b>改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
 * <p>
 * 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
 * </p>
 * <pre>
 * 示例 1：
 *      输入：root = [1,0,2], low = 1, high = 2
 *                  1               1
 *                 / \      ==>      \
 *                0   2               2
 *      输出：[1,null,2]
 *
 * 示例 2：
 *      输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
 *                  3               3
 *                 / \             /
 *                0   4           2
 *                 \        ==>  /
 *                  2           1
 *                 /
 *                1
 *      输出：[3,2,null,1]
 * </pre>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点数在范围 [1, 10^4] 内</li>
 *     <li>0 <= Node.val <= 10^4</li>
 *     <li>树中每个节点的值都是 唯一 的</li>
 *     <li>题目数据保证输入是一棵有效的二叉搜索树</li>
 *     <li>0 <= low <= high <= 10^4</li>
 * </ul>
 *
 * @author c2b
 * @since 2023/5/24 15:04
 */
public class LC0669TrimBST_M {

    public TreeNode trimBST(TreeNode root, int low, int high) {
        //return trimBSTByRecursion(root, low, high);
        return trimBSTByIteration(root, low, high);
    }

    private TreeNode trimBSTByIteration(TreeNode root, int low, int high) {
        while (root != null && (root.val < low || root.val > high)) {
            if (root.val < low) {
                root = root.right;
            } else {
                root = root.left;
            }
        }
        if (root == null) {
            return null;
        }
        // 减左枝
        for (TreeNode currNode = root; currNode.left != null; ) {
            if (currNode.left.val < low || currNode.left.val > high) {
                currNode.left = currNode.left.right;
            } else {
                currNode = currNode.left;
            }
        }
        // 减右枝
        for (TreeNode currNode = root; currNode.right != null; ) {
            if (currNode.right.val < low || currNode.right.val > high) {
                currNode.right = currNode.right.left;
            } else {
                currNode = currNode.right;
            }
        }
        return root;
    }

    private TreeNode trimBSTByRecursion(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            return trimBSTByRecursion(root.right, low, high);
        }
        if (root.val > high) {
            return trimBSTByRecursion(root.left, low, high);
        }
        root.left = trimBSTByRecursion(root.left, low, high);
        root.right = trimBSTByRecursion(root.right, low, high);
        return root;
    }


    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        //root.left.right = new TreeNode(2);
        //root.left.right.left = new TreeNode(1);
        LC0669TrimBST_M lc0669TrimBST_m = new LC0669TrimBST_M();
        TreeNode trimBST = lc0669TrimBST_m.trimBST(root, 3, 4);
        TreeNode.printTree(trimBST);
    }
}
